Possibilistic logic is the most popular approach to represent and reason with uncertain and partially inconsistent knowledge. Regarding normal forms, the encoding of real-world problems does usually not result in a clausal formula and although a possibility nonclausal formula is theoretically equivalent to some possibilistic clausal formula [26, 22], approaches needing clausal form transformations are practically infeasible or have experimentally shown to be highly inefficient as discussed below. Two kinds of clausal form transformation are known: (1) one is based on the repetitive application of the distributive laws to the input non-clausal formula until a logically equivalent clausal formula is obtained; and (2) the other transformation, Tsetin-transformation [59], is based on recursively substituting sub-formulas in the input non-clausal formula by fresh literals until obtaining an equi-satisfiable, but not equivalent, clausal formula.

We propose a generic numerical measure of inconsistency of a database with respect to integrity constraints that is based on a repair semantics. A particular measure is investigated, with mechanisms for computing it via answer-set programs.

In this paper, we propose a general framework, both parameterized and parameter-free, for defining a family of fine-grained inconsistency measures for propositional knowledge bases. The parameterized approach allows to encompass several existing inconsistency mea- sures as specific cases, by properly setting its parameter. And the parameter-free approach is defined to avoid the difficulty in choosing a suitable parameter in practice but still keeps a desired ranking for knowledge bases by their inconsistency degrees. The fine granularity of our framework is based on the notion of MIS partition that considers the inner structure of all the minimal inconsistent subsets of a knowledge base. Moreover, MinCostSAT-based encodings are provided, which enable the use of efficient SAT solvers for the computation of the proposed measures. We implement these algo- rithms and test them on some real-world datasets. The preliminary experimental results for a variety of inputs show that the proposed framework gives a wide range of possibilities for evaluating large knowledge bases.

A semantics is given to possibilistic logic, a logic that handles weighted classical logic formulae, and where weights are interpreted as lower bounds on degrees of certainty or possibility, in the sense of Zadeh's possibility theory. The proposed semantics is based on fuzzy sets of interpretations. It is tolerant to partial inconsistency. Satisfiability is extended from interpretations to fuzzy sets of interpretations, each fuzzy set representing a possibility distribution describing what is known about the state of the world. A possibilistic knowledge base is then viewed as a set of possibility distributions that satisfy it. The refutation method of automated deduction in possibilistic logic, based on previously introduced generalized resolution principle is proved to be sound and complete with respect to the proposed semantics, including the case of partial inconsistency.

Measuring the inconsistency degree of a knowledge base can help us to deal with inconsistencies. Several inconsistency measures have been given under different multi-valued semantics, including 4-valued semantics, 3-valued semantics, LPm and Quasi Classical semantics. In this paper, we first carefully analyze the relationship between these inconsistency measures by showing that the inconsistency degrees under 4-valued semantics, 3-value semantics, LPm are the same, but different from the one based on Quasi Classical semantics. We then consider the computation of these inconsistency measures and show that computing inconsistency measurement under multi-valued semantics is usually intractable. To tackle this problem, we propose two novel algorithms that respectively encode the problems of computing inconsistency degrees under 4-valued semantics (3-valued semantics, LPm) and under Quasi Classical semantics into the partial Max-SAT problems. We implement these algorithms and do experiments on some benchmark data sets. The preliminary but encouraging experimental results show that our approach is efficient to handle large knowledge bases.